#pragma once
#include <stdexcept>
#include "vector_iterator.h"
#include "vector_const_iterator.h"
#include "vector_reverse_iterator.h"
#include "vector_const_reverse_iterator.h"
#include <iostream>
using namespace std;

namespace stl
{
	template<typename T>
	class Vector
	{
		public:
			typedef VectorIterator<T> iterator;
			typedef VectorConstIterator<T> const_iterator;
			typedef VectorReverseIterator<T> reverse_iterator;
			typedef VectorConstReverseIterator<T> const_reverse_iterator;
			Vector() : m_data(nullptr), m_size(0), m_capacity(0) {}
			~Vector() {
				if (m_data != nullptr) delete[] m_data;
				m_size = 0;
				m_capacity = 0;
			}

			T &at(int index) {
				if (index < 0 || index >= m_size) throw std::out_of_range("out of range");
				return m_data[index];
			}

			const T &at(int index) const {
				if (index < 0 || index >= m_size) throw std::out_of_range("out of range");
				return m_data[index];
			}

			T &front() {
				return m_data[0];
			}
			const T &front() const {
				return m_data[0];
			}

			T &back() {
				return m_data[m_size - 1];
			}

			const T &back() const {
				return m_data[m_size - 1];
			}

			T *data() {
				return m_data;
			}

			const T *data() const {
				return m_data;
			}

			T &operator[](int index) {
				return m_data[index];
			}

			const T &operator[](int index) const {
				return m_data[index];
			}

			void push_back(const T &value) {
				if (m_size < m_capacity) {
					m_data[m_size] = value;
					m_size++;
					return;
				}
		
				if (m_capacity == 0) { // 扩容
					m_capacity = 1;
				} else {
					m_capacity <<= 1;
				}
		
				T *data = new T[m_capacity]; // 拷贝旧数组
				for (int i = 0; i < m_size; i++) {
					data[i] = m_data[i];
				}
		
				if (m_data != nullptr) { 
					delete []m_data;
					m_data = nullptr;
				}
		
				m_data = data;
				m_data[m_size] = value;
				m_size++;
			}

			void pop_back() {
				if (m_size > 0) m_size--;
			}	

			void show() const {
				cout << "size = " << m_size << " capacity = " << m_capacity << endl;
				for (int i = 0; i < m_size; i++) {
					cout << m_data[i] << " ";
				}
				cout << endl;
			}

			void assign(int n,const T &value) {
				if (m_capacity >= n) {
					for (int i = 0; i < n; i++) {
						m_data[i] = value;
					}
					m_size = n;
					return;
				}

				if (m_data != nullptr) {
					delete[] m_data;
					m_data = nullptr;
					m_size = 0;
					m_capacity = 0;
				}

				while (m_capacity < n) {
					if (m_capacity == 0) {
						m_capacity = 1;
					} else {
						m_capacity <<= 1;
					}
				}
				m_data = new T[m_capacity];
				for (int i = 0; i < n; i++) {
					m_data[i] = value;
				}
				m_size = n;
			}

			void swap(Vector<T> &other) {
				if (this == &other) return;
				T *data = other;
				int size = other.m_size;
				int capacity = other.m_capacity;
				
				other.m_data = m_data;
				other.m_size = m_size;
				other.m_capacity = m_capacity;

				m_data = data;
				m_size = size;
				m_capacity = capacity;
				return;
			}

			bool empty() const {
				return m_size == 0;
			}

			int size() const {
				return m_size;
			} 

			int capacity() const {
				return m_capacity;
			}

			void resize(int n) {
				resize(n, T());
			}

			void resize(int n, const T &value) {
				if (n < m_size) {
					m_size = n;
					return;
				}

				if (n < m_capacity) {
					for (int i = m_size; i < n; i++) {
						m_data[i] = value;
					}
					m_size = n;
					return;
				}

				while (m_capacity < n) {
					if (m_capacity == 0) {
						m_capacity = 1;
					} else {
						m_capacity <<= 1;
					}
				}

				T *data = new T[m_capacity];
				for (int i = 0; i < m_size; i++) {
					data[i] = m_data[i];
				}
				for (int i = m_size; i < n; i++) {
					data[i] = value;
				}
				if (m_data != nullptr) {
					delete[] m_data;
					m_data = nullptr;
				}
				m_data = data;
				m_size = n;
			}

			void reserve(int n) {
				if (m_capacity > n) return;
				while (m_capacity < n) {
					if (m_capacity == 0) m_capacity = 1;
					else m_capacity <<= 1;
				}
				T *data = new T[m_capacity];
				for (int i = 0; i < m_size; i++) {
					data[i] = m_data[i];
				}
				if (m_data != nullptr) {
					delete[] m_data;
					m_data = nullptr;
				}
				m_data = data;
			}

			// 正向迭代器
			iterator begin() {
				return iterator(m_data);
			}

			iterator end() {
				return iterator(m_data + m_size);
			}

			// 常量正向迭代器
			const_iterator begin() const {
				return const_iterator(m_data);
			}

			const_iterator end() const {
				return const_iterator(m_data + m_size);
			}

			const_iterator cbegin() const {
				return const_iterator(m_data);
			}

			const_iterator cend() const {
				return const_iterator(m_data + m_size);
			}

			// 反向迭代器
			reverse_iterator rbegin() {
				return reverse_iterator(m_data + m_size - 1);
			}

			reverse_iterator rend() {
				return reverse_iterator(m_data - 1);
			}

			// 常量反向迭代器
			const_reverse_iterator rbegin() const {
				return const_reverse_iterator(m_data + m_size - 1);
			}

			const_reverse_iterator rend() const {
				return const_reverse_iterator(m_data - 1);
			}

			const_reverse_iterator crbegin() const {
				return const_reverse_iterator(m_data + m_size - 1);
			}

			const_reverse_iterator crend() const {
				return const_reverse_iterator(m_data - 1);
			}

			// 中间增删
			iterator insert(iterator pos, const T &value) {
				return insert(pos, 1, value);
			}

			iterator insert(iterator pos, int n, const T &value) {
				int size = pos - begin();
				if (m_size + n <= m_capacity) {
					// 移动元素
					for (int i = m_size; i > size; i--) {
						m_data[i + n - 1] = m_data[i - 1];
					}

					for (int i = 0; i < n; i++) {
						m_data[size + i] = value;
					}
					m_size += n;
					return iterator(m_data + size);
				} 

				while (m_size + n > m_capacity) {
					if (m_capacity == 0) m_capacity = 1;
					else m_capacity <<= 1;
				}

				T *data = new T[m_capacity];
				for (int i = 0; i < size; i++) {
					data[i] = m_data[i];
				}
				for (int i = 0; i < n; i++) {
					data[size + i] = value;
				}
				for (int i = size; i < m_size; i++) {
					data[i + n] = m_data[i];
				}

				if (m_data != nullptr) {
					delete[] m_data;
					m_data = nullptr;
				}
				m_data = data;
				m_size += n;
				return iterator(m_data + size);
			}

		iterator erase(iterator pos) {
			if (pos == end()) {
				throw std::out_of_range("out of range");
			}

			// 删除最后一个元素
			if (end() - pos == 1) {
				m_size -= 1;
				return end();
			}

			int size = pos - begin();
			for (int i = size; i < m_size - 1; i++) {
				m_data[i] = m_data[i + 1];
			}
			m_size -= 1;
			return pos;
		}

		iterator erase(iterator first,iterator last) {
			// 对应下标
			int f = first - begin();
			int l = last - begin();
			int n = last - first;
			if (is_basic_type()) {
				memmove(m_data + f, m_data + l, (m_size - l) * sizeof(T));
			}
			else {
				for (int i = 0; i < m_size - l; i++) {
					m_data[f + i] = m_data[l + i];
				}
			}
			m_size -= n;
			return first;
		}

		void clear() {
			m_size = 0; // 析构函数才将数组里面的元素都删除
		}

		private:
			// 优化拷贝
			bool is_basic_type() {
				if (std::is_pointer<T>::value)
					return true;

				return (typeid(T) == typeid(bool)) ||
					   (typeid(T) == typeid(char)) ||
					   (typeid(T) == typeid(unsigned char)) ||
					   (typeid(T) == typeid(short)) ||
					   (typeid(T) == typeid(unsigned short)) ||
					   (typeid(T) == typeid(int)) ||
					   (typeid(T) == typeid(unsigned int)) ||
					   (typeid(T) == typeid(long)) ||
					   (typeid(T) == typeid(unsigned long)) ||
					   (typeid(T) == typeid(float)) ||
					   (typeid(T) == typeid(double));
			}

		private:
			T *m_data;
			int m_size;
			int m_capacity;
	};
}

